package com.zk.algorithm.backtracking;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

@Medium
@LeetCodeExplore
public class LetterCombinationsPfAPhoneNumber {

    public static void main(String...args) {
        LetterCombinationsPfAPhoneNumber solution = new LetterCombinationsPfAPhoneNumber();
        List<String> result = solution.letterCombinations("23");

        Utils.println(result);
    }

    private static final Map<Character, String> map = new HashMap<>();
    static {
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.isEmpty()) {
            return result;
        }

        char[] array = digits.toCharArray();
        backtracking(result, "", array.length, array, 0);

        return result;
    }

    private void backtracking(List<String> result, String curr, int totalLength, char[] array, int i) {
        if (curr.length() == totalLength) {
            result.add(curr);
            return;
        }

        for (char c : map.get(array[i]).toCharArray()) {
            // ==========================
            // BUG: curr + c 而不是 c + curr
            // 否则拼接出来的字符串的顺序会相反
            // ==========================
            backtracking(result, curr + c, totalLength, array, i + 1);
        }
    }

}
